首页 > 试题广场 >

缺失的第一个正整数

[编程题]缺失的第一个正整数
  • 热度指数:76807 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定一个无重复元素的整数数组nums,请你找出其中没有出现的最小的正整数

进阶: 空间复杂度 ,时间复杂度

数据范围:
-2^{31}\le nums[i] \le 2^{31}-1
0\le len(nums)\le5*10^5
示例1

输入

[1,0,2]

输出

3
示例2

输入

[-2,3,4,1,5]

输出

2
示例3

输入

[4,5,6,8,9]

输出

1
/**
方法三:
将有效数字(1 <= val <= N)移动到原本应该所在的位置 [0..N-1]
**/
function minNumberDisappeared( nums ) {
    // write code here
    let temp, N = nums.length, val;
    const swap = (i, j) => {
        temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    for (let i = 0; i < N; i++) {
        while (nums[i] > 0 && nums[i] <= N && nums[i] != i+1 && nums[i] != nums[nums[i]-1]) {
            swap(i, nums[i]-1);
        }
    }
    for (let i = 0; i < N; i++) {
        if (nums[i]!=i+1) {
            return i+1;
        }
    }
    return N+1;
}
发表于 2022-05-26 18:17:57 回复(0)
function minNumberDisappeared( nums ) {
      let obj = {};
      for (let i = 0; i<nums.length; i++) {
         obj[nums[i]] = 1;
      }
      let i = 1;
      while (obj[i]) {
          i++;
      }
      return i; 
 }
module.exports = {
    minNumberDisappeared : minNumberDisappeared
};
发表于 2022-04-22 22:56:37 回复(0)

问题信息

上传者:牛客301499号
难度:
3条回答 4265浏览

热门推荐

通过挑战的用户

查看代码